На плоскости задано множество точек с целочисленными координатами.
Необходимо найти количество отрезков, обладающих следующими
свойствами:
1) оба конца отрезка принадлежат заданному множеству;
2) ни один конец отрезка не лежит на осях координат;
3) отрезок пересекается с обеими осями координат.
Напишите эффективную по времени и по используемой памяти программу
для решения этой задачи.
Программа считается эффективной по времени, если при увеличении
количества точек в k раз время работы возрастает не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти для
хранения всех необходимых данных не зависит от количества точек и не
превышает 1 килобайта.
Перед текстом программы кратко опишите алгоритм решения и укажите
язык программирования и его версию.
Входные данные
В первой строке задаётся N – количество точек в заданном множестве.
Каждая из следующих строк содержит два целых числа x и y – координаты
очередной точки. Гарантируется, что 1 ≤ N ≤ 10000; –1000 ≤ x, y ≤ 1000.
Пример входных данных:
4
6 6
-8 8
-9 -9
7 -5
Выходные данные
Необходимо вывести единственное число: количество удовлетворяющих
требованиям отрезков.
Пример выходных данных для приведённого выше примера входных данных:
2
Решение
Пронумеруем координатные области 1 от до 4.
Область 1 (+,+)
Область 2 (-,+)
Область 3 (-,-)
Область 4 (+,-)
Когда вводится точка, проверяем не лежит ли она на оси.
Если лежит, то просто переходим к вводу очередной точки.
Далее определяем в какой области эта точка находится 1,2,3 или 4. Записываем в массив областей под ее номером, что такая точка уже есть.
Далее смотрим, есть ли точка в противоположной области. Если есть, то увеличиваем количесто отрезков пересекающих обе оси на 1.
var i,k,obl,x,y,N: Integer; Oblast: array[1..4] of boolean; begin ReadLn(N); k:=0; Oblast[1]:=false; Oblast[2]:=false; Oblast[3]:=false; Oblast[4]:=false; for i:=1 to N do begin ReadLn(x,y); if (x=0) or (y=0) then continue; if (x>0) and (y>0) then Obl:=1; if (x<0) and (y>0) then Obl:=2; if (x<0) and (y<0) then Obl:=3; if (x>0) and (y<0) then Obl:=4; Oblast[obl]:=true; if obl=1 then if Oblast[3]=true then k:=k+1; if obl=2 then if Oblast[4]=true then k:=k+1; if obl=3 then if Oblast[1]=true then k:=k+1; if obl=4 then if Oblast[2]=true then k:=k+1; end; end; WriteLn(k); end.